package algorithm;

import java.util.Arrays;

/**
 * K 站中转内最便宜的航班
 * scr : 出发的城市
 * dst : 目的地
 * k : 经过的路线
 * 在最多经过k个节点的情况下找到flights的和的最小值
 */
public class LeetCode_findCheapestPrice_787 {
    /**
     * 可行
     * 使用二维数组g[i][j]，表示经过i次转机到达j这个位置总的花费
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k ：转机的此时，意味着需要经过k + 1个节点
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INM = Integer.MAX_VALUE / 2;
        int[][] g = new int[k + 2][n];
        for (int i = 0; i < k + 2; i++) {
            Arrays.fill(g[i], INM);
        }
        g[0][src] = 0;

        // k原来的意义是转机的次数，将这个值 + 2 之后表示经过的节点数，值 + 1表示要经过的路径数量
        for(int j = 1; j < k + 2; j++) {
            for (int[] t : flights) {
                int x = t[0], y = t[1], cost = t[2];
                g[j][y] = Math.min(g[j][y], g[j - 1][x] + cost);
            }
        }
        int res = INM;
        for (int i = 1; i < k +2; i++) {
            res = Math.min(g[i][dst], res);
        }
        return res == INM ? -1 : res;
    }

    /**
     * 不可行
     * 一维数组g[i]表示到达i目的地总的花费
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @param noUse ：避免因为方法名相同而报错，用来实现重载的，没有什么作用
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k, int noUse) {
        int INM = Integer.MAX_VALUE / 2;
        int[] g = new int[n];
        Arrays.fill(g, INM);
        g[src] = 0;

        for (int j = 1; j < k + 2; j++) {
            for (int[] flight : flights) {
                int x = flight[0], y = flight[1], cost = flight[2];
                g[y] = Math.min(g[y], g[x] + cost);
            }
        }
        int res = INM;
        for (int i = 1; i < k + 2; i++) {
            res = Math.min(g[dst], res);
        }
        return res == INM ? -1 : res;
    }
}



















